阿~~有逐漸上手jacascript的感覺啊...真是開心,今天就把Gray Code實作出來吧: 目
用Javascript征服演算法 (2-Gray Code-Javascript實作)
看完上一篇的Gray Code解法後,是不是非常躍躍欲試啊!!!!(摩拳擦掌)
首先在實作之前,我們就來分析分析我們的解法中,需要那些功能吧(方便模組化)
其實就是如此的簡單啊!!!!!!!!!!!!!!!!(跟上一個遞迴比XDDD)
OKOK 那就來針對逐一功能寫code吧!
首先建立了一個Gray function來當最作待會Object的建構子
function Gray(code, isOdd) {
this.code = code;
this.isOdd = isOdd;
}
接下來就是初始化一下我們的init array吧
//initial array
var my_array = new Array();
for (i = 0; i < length; i++) {
my_array[i] = 0;
}
var init = new Gray(my_array,
true);
再來判斷奇數列or偶數列,因為我們利用物件屬性,可以直接來判斷為奇或偶
this.isOdd ? ' odd' : ' even'
最重要的2-1 2-2功能就寫在一起囉
//奇數列i就表示為最後一位元(length - 1)
//偶數列就是最右往左邊數為1得數字的左邊那個(所以減1位數)
//-1則是在Gray code最後一組只有最左邊的數字為1其餘為0的狀況下,lastIndexOf(1)才會為0
var i = (this.isOdd ? this.code.length : this.code.lastIndexOf(1)) - 1;
console.log(this.code.lastIndexOf(1));
return new Gray(i === -1 ? [] :
this.code.slice(0, i)
.concat([1 - this.code[i]])
.concat(this.code.slice(
i + 1, this.code.length)),
!this.isOdd);
在這邊特別說明一下上面實作變換位元的部分
this.code.slice(0, i)
.concat([1 - this.code[i]])
.concat(this.code.slice(
i + 1, this.code.length))
這邊用了slice跟concat就能統整出一個對於奇偶數列的統一解法,透過i的計算,第一個slice是將陣列從左邊數過來到第i個位數之前取出來,因此如果為奇數列就是最後一個位數之前的數值取出來,而後的concat就加上是1就為0,是0就為1的結果,因此奇數列在此已經解決
而在偶數列部分,因為i是需要變動的位數,因此也是將i位數值之前的值取出來,轉變0->1, 1->0後,再加上後面的位數,就完成下一列的變化: )
最後寫點recursive讓他自動去跑完所有組別吧
function successors(gray) {
var nx = gray.next();
//等到最後一組產生空陣列後才會將所有組別回傳
return nx.code.length === 0 ? [] : [nx].concat(successors(nx));//稍微用到一點recursiveXD
}
附上能夠執行的所有程式碼囉: )
//建構式
function Gray(code, isOdd) {
this.code = code;
this.isOdd = isOdd;
}
Gray.prototype.toString = function() {
return this.code + (this.isOdd ? ' odd' : ' even');
};
Gray.prototype.next = function() {
//奇數列i就表示為最後一位元(length - 1)
//偶數列就是最右往左邊數為1得數字的左邊那個(所以減1位數)
//-1則是在Gray code最後一組只有最左邊的數字為1其餘為0的狀況下,lastIndexOf(1)才會為0
var i = (this.isOdd ? this.code.length : this.code.lastIndexOf(1)) - 1;
console.log(this.code.lastIndexOf(1));
return new Gray(i === -1 ? [] :
this.code.slice(0, i)
.concat([1 - this.code[i]])
.concat(this.code.slice(
i + 1, this.code.length)),
!this.isOdd);
};
function gray(length) {
function successors(gray) {
var nx = gray.next();
//等到最後一組產生空陣列後才會將所有組別回傳
return nx.code.length === 0 ? [] : [nx].concat(successors(nx));//稍微用到一點recursiveXD
}
//initial array
var my_array = new Array();
for (i = 0; i < length; i++) {
my_array[i] = 0;
}
var init = new Gray(my_array,
true);
return [init].concat(successors(init));//[init]是在object外再加一層[]這樣才會變成array,因為concat需要由array來呼叫
}
gray(4).forEach(function(code) {
//alert(code);
});
以上就是Gray Code的實作囉~大家有沒有懂阿
時間有限就只做這個解法,另外一個解法大家可以試試看練習寫javascript來解喔!!!!
附上我的Jsfiddle連結~(怕大家討厭彈跳視窗,要執行前記得把最下面的//alert()拿掉唷)
http://jsfiddle.net/stanney/Ft3yn/3/
var newcode = this.code.slice(0);
newcode[i] = 1-newcode[i];
這樣就可以做出新的array,省了兩次concat,參考一下。